#include <bits/stdc++.h>

using namespace std;

// https://www.luogu.com.cn/problem/CF369D

class Solution
{
public:
    int minCost(vector<int> &nums)
    {
        int n = nums.size();
        // 往 nums 末尾追加 0，防止 DP 过程中超出下标范围
        for (int i = 1; i <= 3; i++)
            nums.push_back(0);

        const long long INF = 1e18;
        long long f[n + 3][n + 3];
        for (int i = 0; i <= n + 2; i++)
            for (int j = 0; j <= n + 2; j++)
                f[i][j] = INF;
        // 一开始 i = 0, j = 1
        f[0][1] = 0;

        auto update = [&](long long &a, long long b)
        { a = min(a, b); };

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
            {
                // 套 DP 方程
                update(f[j + 1][j + 2], f[i][j] + max(nums[i], nums[j]));
                update(f[j][j + 2], f[i][j] + max(nums[i], nums[j + 1]));
                update(f[i][j + 2], f[i][j] + max(nums[j], nums[j + 1]));
            }

        long long ans = INF;
        for (int i = n; i < n + 3; i++)
            for (int j = n; j < n + 3; j++)
                update(ans, f[i][j]);
        return ans;
    }
};

// 作者：TsReaper
// 链接：https://leetcode.cn/problems/find-minimum-cost-to-remove-array-elements/solutions/3591270/jie-fa-dp-by-tsreaper-h1tn/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

int main()
{
    vector<int> v({10, 8, 10, 10, 9, 7, 6});
    cout << Solution().minCost(v) << endl;
    return 0;
}
